package com.nowcoder.code.lcof;

import com.algorithm.model.TreeNode;
import com.algorithm.model.TreeNodeService;

public class JZ37 {


    public static void main(String[] args) {
        TreeNode treeNode = TreeNodeService.getTreeByArray(new int[]{10, 6, 14, 4, 8, 12, 16});
        JZ37 jz37 = new JZ37();
        String s = jz37.Serialize(treeNode);
        TreeNodeService.print(jz37.Deserialize(s));
    }

    String Serialize(TreeNode root) {
        if (root == null) {
            return "{#}";
        }
        String left = Serialize(root.left);
        String right = Serialize(root.right);
        StringBuilder sb = new StringBuilder("{").append(root.val).append(",").append(left).append(",").append(right).append("}");
        return sb.toString();
    }


    TreeNode Deserialize(String str) {
        if (str == null || str.isEmpty() || str.equals("{#}")) {
            return null;
        }

        int i = 1;
        Integer j = null;
        for (; i < str.length(); i++) {
            if (j != null && j == 0) {
                break;
            }
            char ci = str.charAt(i);
            if (ci == '{') {
                if (j == null) {
                    j = 0;
                }
                j++;
            }
            if (ci == '}') {
                if (j == null) {
                    return null;
                }
                j--;
            }
        }
        int s = str.indexOf(',');

        TreeNode treeNode = new TreeNode(Integer.parseInt(str.substring(1, s)));
        treeNode.left = Deserialize(str.substring(s + 1, i));
        treeNode.right = Deserialize(str.substring(i+1, str.length() - 1));

        return treeNode;
    }

}
